"""
给定一个正整数n，计算出小于等于n的质数有多少个。 比如17，则返回7，因为小于等于17的质数有2，3，5，7，11, 13，17

"""

# O(n**2)
def count_prime(n):
    is_prime = [True] * (n +1)
    i = 2
    while(i*i < n):
        j = i
        while(i*j<n):
            is_prime[i*j] = False
            j = j+1
        i = i+1
    print(is_prime)
    cnt = 0
    for i in range(2,n+1):
        if is_prime[i]:
            print(i,end='  ')
            cnt = cnt+1
    return cnt

print(count_prime(17))